import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName KP35_hasPathSum
 * @Description: TODO
 * @Author: JCC
 * @CreateTime: 2023/11/1 11:51
 */
public class KP36_PathSum {
    // 测试链接：https://leetcode.com/problems/path-sum-ii

    public static class TreeNode {
        public int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        List<Integer> path = new ArrayList<>();
        pathSumChild(root, 0, targetSum, path, ans);
        return ans;
    }

    public void pathSumChild(TreeNode root, int preSum, int targetSum, List<Integer> path, List<List<Integer>> ans) {
        // 判断是否为叶子结点
        if (root.left == null && root.right == null) {
            if (preSum + root.val == targetSum) {
                path.add(root.val);
                ans.add(copyArray(path));
                path.remove(path.size() - 1);
            }
            return;
        }
        // 非叶子结点
        preSum += root.val;
        path.add(root.val);
        if (root.left != null) {
            pathSumChild(root.left, preSum, targetSum, path, ans);
        }
        if (root.right != null) {
            pathSumChild(root.right, preSum, targetSum, path, ans);
        }
        path.remove(path.size()-1);
    }

    public List<Integer> copyArray(List<Integer> path) {
        List<Integer> copy = new ArrayList<>();
        for (Integer num : path) {
            copy.add(num);
        }
        return copy;
    }
}
